[Coding035] LeetCode 86

Partition List

More coding records

Get the knowledge flowing and circulating! :)

目录

※ 本题收获

• 如果思考超时，要立刻看解析，这点要牢记！

• 清晰的思路不一定能够用清晰的代码表达；能够用清晰的代码表达清晰的思路，这才是高手！

题目：86. Partition List

Given the head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

Example 1:

xxxxxxxxxx
2
1
Input: head = [1,4,3,2,5,2], x = 3
2
Output: [1,2,2,4,3,5]

Example 2:

xxxxxxxxxx
2
1
Input: head = [2,1], x = 2
2
Output: [1,2]

Constraints:

• The number of nodes in the list is in the range [0, 200].

• -100 <= Node.val <= 100

• -200 <= x <= 200

代码1（配 · 手绘过程图）

xxxxxxxxxx
43
1
/**
2
 * Definition for singly-linked list.
3
 * public class ListNode {
4
 *     int val;
5
 *     ListNode next;
6
 *     ListNode() {}
7
 *     ListNode(int val) { this.val = val; }
8
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9
 * }
10
 */
11
class Solution {
12
    public ListNode partition(ListNode head, int x) {
13
        
14
        if (head == null || head.next == null)
15
            return head;
16

17
        ListNode dummy1 = new ListNode(0);
18
        ListNode dummy2 = new ListNode(0);
19

20
        dummy1.next = head;
21

22
        ListNode p = dummy1;
23
        ListNode q = dummy2;
24

25
        while (p.next != null)
26
        {
27
            if (p.next.val < x)
28
            {
29
                ListNode r = p.next;
30
                p.next = r.next;
31
                q.next = r;
32
                q = q.next;
33
            }
34
            else
35
            {
36
                p = p.next;
37
            }
38
        }
39
        q.next = dummy1.next;
40

41
        return dummy2.next;
42
    }
43
}

代码解读 | 评价

解题思路

• 代码有点复杂，不够清晰；

• p、q、r这3个指针虽然有逻辑，但是没法让自己一看就能看得十分清楚！

复杂度分析

代码2（配 · 手绘过程图）

xxxxxxxxxx
38
1
/**
2
 * Definition for singly-linked list.
3
 * public class ListNode {
4
 *     int val;
5
 *     ListNode next;
6
 *     ListNode() {}
7
 *     ListNode(int val) { this.val = val; }
8
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9
 * }
10
 */
11
class Solution {
12
    public ListNode partition(ListNode head, int x) {
13
        ListNode beforeHead = new ListNode(0);
14
        ListNode afterHead = new ListNode(0);
15
        ListNode before = beforeHead;
16
        ListNode after = afterHead;
17

18
        while (head != null)
19
        {
20
            if (head.val < x)
21
            {
22
                before.next = head;
23
                before = before.next;
24
            }
25
            else
26
            {
27
                after.next = head;
28
                after = after.next;
29
            }
30
            head = head.next;
31
        }
32

33
        after.next = null;
34
        before.next = afterHead.next;
35

36
        return beforeHead.next;
37
    }
38
}

代码解读 | 评价

• 代码比较清晰。十分舒爽！

复杂度分析